\chapter{Cryptosystème de Mc Eliece}

	Le cryptosystème de Mc Eliece mis au point en 1978 est est l'un des premiers systèmes de cryptage à clef publique.
	Son principe repose sur l'utilisation de codes correcteurs d'erreurs, plus particulièrement des codes de Goppa.
	Ce cryptosystème est fréquemment comparé au système RSA, puisqu'inventé presqu'au même moment.
	La différence de taille des clefs entre ces deux systèmes pour un même niveau de sécurité à jusqu'ici grandement pénalisé le développement du cryptosystème de Mc Eliece.
	Néanmoins, des projets comme celui de l'OTAN \footnote{Projet OTAN : SPS 984520 Secure implementation of post-quantum cryptography} remettent au jour ce système pouvant résister à l'avènement d'ordinateurs quantiques. 
	C'est ce cryptosytème que nous avons étudié.

	\section{Les clefs}
		Un cryptage asymétrique repose sur un principe simple :
		tout le monde a accès à une clef publique permettant le chiffrement et seul le créateur de cette clef possède la clef privée permettant le déchiffrement.

		Pour ce faire, on commence par créer G la matrice génératrice d'un code de Goppa de paramètres :
		\begin{itemize}
			\item k dimension du bloc de message à coder
			\item n dimension du bloc de message à envoyer
			\item t la capacité de correction
		\end{itemize}
		La clef privée représente l'ensemble :
		\begin{itemize}
			\item G matrice génératrice (n,k)
			\item P une matrice (n,n) de permutation
			\item Q une matrice (k,k) inversible 
		\end{itemize}
		La clef publique partagé est l'ensemble :
		\begin{itemize}
			\item G'=PGQ
			\item La capacité de correction t
		\end{itemize}

	\section{Le chiffrement}
		Soit  $ m \in \mathbf{F}_{2}^{k} $  le message à chiffrer, l'envoyeur calcule l'image du message par le code G 
		puis ajoute un vecteur  $ e \in \mathbf{F}_{2}^{n} $  de poids inférieur à t.
		 $$ x = G'm + e = PGQm + e $$ 
		C'est ce vecteur  $ x \in \mathbf{F}_{2}^{n} $  qui correspond au message chiffré.

	\section{Le déchiffrement}
		Soit  $ x \in \mathbf{F}_{2}^{n} $  le message chiffré reçu, on calcule :
		 $$  P^{-1}x = GQm + P^{-1}e $$ 
		Le vecteur  $ GQm \in \mathbf{F}_{2}^{n} $  est un mot du code de Goppa 
		et donc  $ P^{-1}e \in \mathbf{F}_{2}^{n} $  est un vecteur d'erreur de poids inférieur à t car P matrice de permutation.
		On utilise notre algorithme efficace de décodage du code de Goppa, on obtient donc   $ Qm $ , 
		connaissant  $ Q $  inversible on a :
		 $$  m = Q^{-1}Qm $$ 
		D'où le déchiffrement.

	\section{Le principe de sécurité}
		Le cryptosystème de Mc Eliece repose sur 2 problèmes difficiles mathématiques.
		Premièrement, la difficulté à partir d'une matrice  $ G'=PGQ $  de retrouver la matrice G en temps polynomial.
		Secondement, de décoder un code correcteur qui parait aléatoire, c'est le problème de reconnaissance du syndrome que nous avons évité en utilisant un code de Goppa dont on connaît la structure et donc un algorithme efficace de décodage.

		\subsection{Problème de reconnaissance du code de Goppa}

			\cite{finiasz} Quand on parle de l'indistinguabilité d'un code de Goppa permuté, il s'agit de reconnaître un code de Goppa sans la donnée de son support ni de g.
			Dans notre cas, il s'agit de retrouver la structure du code à partir de la matrice génératrice ou de parité permutée.
			On peut formaliser le problème ainsi :

			\begin{pb}
				Soit $H_{g} $, la matrice de parité d'un code de Goppa de polynôme g ordonnée.
				Un distingueur de code de Goppa est un algorithme prenant en entrée une matrice H'.
				Ce distingueur doit vérifier avec une bonne probabilté s'il existe un triplet (g,P,Q) tel que :
				\begin{eqnarray*}
					P  &\in& S_{n}(\mathbb{F}) \\
					Q  &\in& GL_{k}(\mathbb{F})\\
					H' &=& PH_{g}Q
				\end{eqnarray*}
			\end{pb}

			Aucun distingueur sous exponentiel n'est connu à ce jour.
			Les meilleurs distingueurs consistent en une recherche exhaustive de codes de Goppa ayant des paramètres communs et de tester l'équivalence.

		\subsection{Problème du décodage par syndrome} 

			\cite{veron} L'objectif est de montrer que le problème de caractérisation du syndrome suivant est NP-complet.

			\begin{pb}
				Soit H une matrice (k,n) de parité d'un code correcteur linéaire.
				Soit y un vecteur de $\mathbb{F}^{n}$.
				On cherche l'unique $\epsilon$ tel que :
				\begin{eqnarray*}
					Hy &=& H\epsilon\\
					\mathbf{d}(\epsilon) &<& t
				\end{eqnarray*}
			\end{pb}

			Dans la théorie de la NP-complétude, au problème dit d'optimisation énoncé ci-dessus on associe le problème de décision suivant.

			\begin{pb}
				Soit H une matrice (k,n) de parité d'un code correcteur linéaire.
				Soit y un vecteur de $\mathbb{F}^{n}$.
				On cherche s'il existe $\epsilon$ tel que :
				\begin{eqnarray*}
					Hy &=& H\epsilon\\
					\mathbf{d}(\epsilon) &<& t
				\end{eqnarray*}
			\end{pb}

			Ce problème à été réduit polynomialement au problème dit des trois mariages suivant par Mc Eliece, Berlekamp et Van Tilborg.

			\begin{pb}
				Soit T un ensemble fini.
				Soit U $\subset$ $T\times T \times T$.
				On cherche s'il existe W tel que :
				\begin{eqnarray*}
					W &\subset& U \\
					card(W) &=& card(T) \\
					\forall (x,y) \in W^{2}, \forall i, x_{i} &\neq& y_{i}
				\end{eqnarray*}
			\end{pb}

			Ce problème étant NP-complet, le problème de décision associé au problème du décodage par syndrome l'est aussi.
			Donc à fortiori le problème de décodage par syndrome est NP-complet.